1. Field of the Invention
This invention relates generally to optimizing compilers for development of computer programs for use on a computer, and more particularly to value numbering.
2. Description of the Related Art
A problem addressed by the optimizing compiler prior art is redundancy. Redundancy may take two forms. An expression is redundant, also known as full redundancy, if the expression has been evaluated before in a program on all paths leading to the expression. An expression is partially redundancy if the expression has been evaluated before in a program on some, but not all paths, leading to the expression. An objective of an optimizing compiler relative to redundancy is to remove the redundant expression so that it is not executed, thus saving memory which would otherwise store the redundant expression and saving execution time which would otherwise be used to execute the redundant expression. The objective relative to a partial redundancy is to move the expression so that it is no longer partially redundant.
Redundancy optimization may be understood by reference to the optimizing compiler art. FIG. 1 illustrates a procedure for translating a program to create an executable binary object program 12. A lexical/syntax analysis is conducted to transform source program to a first intermediate language program 16. First intermediate language program 16 is then processed by an optimization routine 18 to create a second intermediate language program 20, which is then directly interpreted by the code generation routine 22 to create object program 12.
Optimization routine 18 is illustrated in FIG. 2 as it is understood in the art. Optimization processing is achieved by first performing a control flow analysis in routine 27 of first intermediate language 16. Control flow analysis routine 24 provides the control flow data 26, which are then passed to a data-flow analysis routine 28 wherein first intermediate language program 16 is analyzed for data flow. Data-flow analysis routine 28 produces the data-flow data 30. Finally, a program transformation procedure 32 accepts control flow data 26, data-flow data 30, and first intermediate language program 16 to produce second intermediate language program 20. Optimization routine 18 may include prior techniques for redundancy optimization using the control flow data 26 and the data-flow data 30 to enable the program transformation procedure 32 to perform redundancy optimization.
Many methods for redundancy optimization are known in the art. For instance, in Morel et al. (E. Morel and C. Renvoise, "Global Optimization by Suppression of Partial Redundancies", Communications of the ACM, vol. 22, no. 2, February 1979, p. 96-103) redundancy suppression and moving is accomplished by iteratively solving simultaneous Boolean systems in which each basic block and each expression within a basic block are assigned Boolean properties. Intra-basic block or local Boolean assigned properties include transparency, local availability, and local anticipability. Corresponding inter-basic block or global Boolean properties are also assigned. Morel et al. suggests that the average number of iterations to solve such simultaneous Boolean systems is 4.75 iterations, and as low as three iterations for well-structured programs. However, the teachings of Morel et al. only suppress and move redundancies that are lexically the same.
In Rosen et al. (B. Rosen, M. Wegman, and K. Zadeck, "Global Value Numbers and Redundant Computations", Fifteenth ACM Principles of Programming Languages Symposium, Jan. 12-27, 1988, San Diego, Calif.), a program is translated into Static Single Assignment Form (SSA). See Cytron et al. (R. Cytron and J. Ferrante, "An Efficient Method for Computing Static Single Assignment Form", Sixteenth Annual ACM Symposium on Principles of Programming Languages Symposium, Jan. 25-35, 1989). All expressions are attempted to be moved upwards. Value numbering is then performed locally in basic blocks. Redundancy or partial redundancy is discovered after expressions are attempted to be moved. Although the technique of Rosen et al. may identify redundancies based on the same value number in addition to those that are lexically the same, it does so by attempting to move and scanning all expressions.
Alpern et al. (B. Alpern, N. Wegman, and F. Zadeck, "Detecting Equality of Values in Programs", Conf. Rec. Fifteenth ACM Symposium on Principles of Programming Languages Symposium, Jan. 1-11, 1988) teach representing the symbolic execution of a program as a finite state machine and applying a partitioning technique to minimize the finite state machine in order to detect an equivalence of variables in the program. Although this technique is computational intensive, Alpern et al. suggest that the problem of detecting the equivalence of variables in the program is undecidable.
Thus, practitioners in the art generally employ computationally intensive techniques for code motion and code redundancy removal, and there is an accordingly clearly-felt need in the art for more efficient compiling procedures providing code motion and code redundancy removal at a reasonable compile-time cost.